package src.CodeTop;

/**
 *
 */

public class _143ReorderList {
    public static void main(String[] args) {

    }

    public void reorderList(ListNode head) {
        // 校验合法性
        if (head == null || head.next == null || head.next.next == null) {
            return;
        }
        // 先使用快慢指针找到链表的中点
        ListNode fast = head, slow = head;
        // 当快指针未遍历完时进入循环
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 通过慢指针(也即中点)断开链表
        ListNode newHead = slow.next;
        slow.next = null;
        // 翻转后半部分链表
        newHead = reverseLinkedList(newHead);
        // 重排链表，依次连接两个链表即可
        while (newHead != null) {
            // 标记后链表的下一个结点
            ListNode temp = newHead.next;
            // 现将后链表头结点连到前链表二结点上
            newHead.next = head.next;
            // 再将前链表头结点到后链表当前头结点上
            head.next = newHead;
            // 再将前后两链表头结点平行右移
            head = newHead.next;
            newHead = temp;
        }
    }

    public ListNode reverseLinkedList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode tail = head.next;
        ListNode p = reverseLinkedList(head.next);
        head.next = tail.next;
        tail.next = head;
        return p;
    }
}
